package linkList;

public class Solution_1 {
    /**
     * 链表是一种通过指针串联在一起的线性结构，以单链表为例：每一个节点由两部分组成，
     * 一个是数据域一个是指针域（存放指向下一个节点的指针），
     * 最后一个节点的指针域指向null（空指针的意思）。
     * 链表的入口节点称为链表的头结点也就是head。
     * 循环链表可以用来解决约瑟夫环问题
     * 链表在内存中是不连续存放的，通过指针链接内存中分布的各节点.
     * 适合于数据量不固定，插入和删除操作频繁，查找操作相对不频繁的场景。
     */
    /**
     * 203. 移除链表元素 -easy
     * @param head
     * @param val
     * @return
     * 在单链表中移除头结点 和 移除其他节点的操作方式是不一样
     * 那么可以设置一个虚拟头结点，
     * 这样原链表的所有节点就都可以按照统一的方式进行移除了。
     */
    //1.直接使用原来链表进行移除操作
    public ListNode removeElements(ListNode head, int val) {
        //从头节点开始判断，如果head 是val节点，就head后移动
        while(head != null && head.val == val) {
            //如果head 是val节点，就head后移动
            head = head.next;
        }
        //出循环后，head指向第一个不是val的节点
        //待会要返回第一个不是val的节点位置，所以用cur来移动
        ListNode cur = head;
        while(cur != null && cur.next != null) {
            //这里的next老是忘了写，可以想到
            //前一个while循环后,head 已经指向了第一个不是val的节点
            //所以这里是判断cur.next.val == val
            if(cur.next.val == val) {
                cur.next = cur.next.next;
            } else {
                cur = cur.next;
            }
        }
        return head;
    }
    //2.使用虚拟头结点
    public ListNode removeElements1(ListNode head, int val) {
        //创建虚拟头结点 指向head,使得头节点和其他节点操作一致
        ListNode dummy = new ListNode(-1, head);
        ListNode cur = dummy;
        while(cur.next != null) {
            if(cur.next.val == val) {
                cur.next = cur.next.next;
            } else {
                cur = cur.next;
            }
        }
        return dummy.next;
    }

    /**
     * 707. 设计链表 -medium
     */
    class ListNode{
        int val;
       ListNode next;
        ListNode(int val){
            this.val=val;
        }
        ListNode(int val, ListNode next){
            this.val=val;
            this.next=next;
        }
    }
    class MyLinkedList {
        int size; //链表长度
        ListNode head; //注意这里是虚拟头结点

        public MyLinkedList() {
            size=0;
            head = new ListNode(0);

        }
        //get(index)：获取链表中第 index 个节点的值。索引从 0 开始。
        // 如果索引无效，则返回-1。
        public int get(int index) {
            if (index < 0 || index >= size) {
                return -1;
            } else {
                //索引值有效
                //从虚拟头结点开始遍历 所以用<=
                ListNode cur = head;
                for (int i = 0; i <= index; i++) {
                    cur = cur.next;
                }
                return cur.val;
            }
        }

        public void addAtHead(int val) {
            ListNode newNode = new ListNode(val);
            newNode.next = head.next;
            head.next = newNode;
            size++;

        }

        public void addAtTail(int val) {
            ListNode newNode = new ListNode(val);
            ListNode cur = head;
            while (cur.next != null) {
                cur = cur.next;
            }
            //循环结束后，cur指向了最后一个节点
            cur.next = newNode;
            size++;

        }

        public void addAtIndex(int index, int val) {
            if(index < 0 || index > size) {
                return;
            } else {
                ListNode newNode = new ListNode(val);
                //找到要插入位置的前一个节点
                //参考get(index)
                ListNode preNode = head;
                for (int i = 0; i < index; i++) {
                    preNode = preNode.next;
                }
                newNode.next = preNode.next;
                preNode.next = newNode;
                size++;
            }

        }

        public void deleteAtIndex(int index) {
            if(index < 0 || index >= size) {
                return;
            } else {
                //删除有效索引节点
                //还是找前一个节点
//                //为了防止删除头节点的next.next空指针异常
//                if(index == 0) {
//                    //这个if内只有size > index的情况即，size > 0的情况
//                    head = head.next;
//                    size--;
//                    return;
//                }
                ListNode preNode = head;
                for (int i = 0; i < index; i++) {
                    preNode = preNode.next;
                }
                preNode.next = preNode.next.next;
                size--;
            }

        }
    }
}
